package it.storm.solution;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 84. 柱状图中最大的矩形
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 */
public class Solutions_84 {
    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};  // output: 10
        int result = largestRectangleArea(heights);
        System.out.println(result);
    }

    /**
     * 解法二：单调栈（14ms）
     * 关键：保证栈中元素都是递增的，存储的是每个柱子所在的索引
     * 维护单调栈：遍历的柱子高度小于栈顶索引上的柱子高度时，那么计算面积：高度 * 柱子数量
     * 1. 高度 = 弹栈操作，弹出来的元素就是要计算的柱子所在索引，得到其高度
     * 2. 柱子数量 = [右边界 - 左边界 + 1]
     *      左边界：索引向左扩展时，第一个遇到的比其矮的柱子所在索引
     *      右边界：索引向右扩展时，第一个遇到的比其矮的柱子所在索引
     * 3. 单调栈的作用：要计算的柱子弹栈后，此时的栈顶元素，就是要计算柱子的左边界索引了
     */
    public static int largestRectangleArea(int[] heights) {
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        int len = heights.length;
        if (len == 1) {
            return heights[0];
        }
        // 为方便第一个柱子与最后一个柱子的计算，重新建立数组，包含前后虚拟柱子（高度为默认值 0）
        int[] arr = new int[len + 2];
        // 将 heights 数组从索引 0 开始的 len 个元素复制到 arr 数组的 [1, len] 区间中
        System.arraycopy(heights, 0, arr, 1, len);
        for (int i = 0; i < arr.length; i++) {
            // 判断当前柱子高度，是否小于栈顶的柱子高度
            while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                // 栈顶柱子的高度（对该柱子能够勾勒出的最大矩形面积进行计算）
                int h = arr[stack.pop()];
                // 弹出要计算的柱子时，此时栈顶元素就是【要计算柱子的左边界所在索引，即左侧第一个小于其高度的柱子】
                // 为什么要减 1？虚拟头柱子的 1 个单位，不参加计算
                res = Math.max(res, h * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        return res;
    }

    /**
     * 解法一：暴力法（985ms）
     * 对每个柱子，都进行最大矩形面积的计算
     */
    public static int largestRectangleArea2(int[] heights) {
        int res = 0;
        int len = heights.length;
        if (len == 1) {
            return heights[0];
        }
        for (int i = 0; i < len; i++) {
            // count 记录与 i 相邻的大于等于 heights[i] 高度的柱子数量
            int count = 1, j = i;
            int cur = heights[i];
            // 以 i 为中心，向左侧扩展，直到左侧柱子的高度小于当前柱子高度
            while (j > 0 && heights[j - 1] >= cur) {
                j--;
                count++;
            }
            j = i;
            // 以 i 为中心，向右侧扩展，直到右侧柱子的高度小于当前柱子高度
            while (j < len - 1 && heights[j + 1] >= cur) {
                j++;
                count++;
            }
            // 当前 i 柱子能够构成的最大面积 = 高度 * 柱子数量
            res = Math.max(res, heights[i] * count);
        }
        return res;
    }
}
